import java.util.Arrays;

/**
 * 插入排序
 *
 * @Author: wanqian
 * @Date: 2021/2/1 1:19
 */
public class InsertSort {
    public static int[] arr = {4, 3, 65, 12, 1, -6, 46, 64};

    public static void main(String[] args) {
        int[] arr = new int[100000];
        for (int i = 0; i < 100000; i++) {
            arr[i] = (int) (Math.random() * 10000);
        }
//        System.out.println("排序前" + Arrays.toString(arr));
        long start = System.currentTimeMillis();
        insertSort(arr);
        long end = System.currentTimeMillis();
        long consume = (end - start);
        System.out.println("耗时" + consume + "毫秒");
        System.out.println("排序后" + Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        int value;
        int index;
        //从第二个数开始与前面所有数进行比较排序
        for (int i = 1; i < arr.length; i++) {
            //记录当前元素的值
            value = arr[i];
            //指针从前一个数开始向前比较
            index = i - 1;
            //若指针所指元素大于value,则将其向后移动一位
            //value中记录了当前元素的值,所以不用担心数据被覆盖
            while (index >= 0 && arr[index] > value) {
                arr[index + 1] = arr[index];
                index--;
            }
            //当遇到较小的元素或已遍历完(index = -1)
            //则将value放在arr[index + 1]
            arr[index + 1] = value;

//            System.out.println(String.format("第%d次排序：%s", i, Arrays.toString(arr)));
        }
    }

    /**
     * 交换排序算法
     * 核心思想依然是分为一个有序表和一个无序表
     * 每次将新加入的数从最大的数开始比较，若小于则交换位置，然后再与第二大的数比较，依次进行
     * 经过实际测试不如插入排序，可能是由于while中赋值语句更多
     *
     * @param arr
     */
    public static void insertSort2(int[] arr) {
        int temp;
        int index;
        for (int i = 1; i < arr.length; i++) {
            index = i - 1;
            while (index >= 0 && arr[index] > arr[index + 1]) {
                temp = arr[index];
                arr[index] = arr[index + 1];
                arr[index + 1] = temp;
                index--;
            }
//            System.out.println(String.format("第%d次排序：%s", i, Arrays.toString(arr)));
        }
    }
}
